#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>

using namespace std;

string next(string, int);
bool lessthan(char, char);
string mysort(string s, int len);

int main()
{
  int numcases;
  cin >> numcases;
  string s;
  getline(cin, s);
  for(int i=0; i<numcases; i++)
  {
    getline(cin, s);
   
    while (s[0] == ' ') s.erase(0, 1);
    while (s[s.length()-1] == ' ') s.erase(s.length()-1, 1);
    int len = s.length();
   
    s = mysort(s, len);

    while(true)
    {         
      cout << s << "\n";
      s = next(s,len);
      if(s == "")
        break;
    }
  }
  return 0;
}

string next(string in, int len)
{
    string result="";
    char m,n;
    int pos1=-1, pos2=-1;
    for(int j=len-1; j>=1; j--)
    {
      n = in[j];
      for(int i=j-1; i>=0; i--)
      {
        m = in[i];
        if(lessthan(m, n) && i > pos1)
        {
          pos1 = i;
          pos2 = j;
        }
      }
    }
    if(pos1 != -1)
    {
      char temp = in[pos1];
      in[pos1] = in[pos2];
      in[pos2] = temp;
      result+=in.substr(0, pos1+1);

      char temp2[len - pos1 - 1];
      for(int k=pos1+1; k<len; k++)
        temp2[k-pos1-1] = in[k];

      sort(temp2, temp2+len-pos1-1, lessthan);
      for(int k=0; k<len-pos1-1; k++)
        result+=temp2[k];
    }
    return result;
}

inline bool lessthan(char a, char b)
{
  char a2 = tolower(a);
  char b2 = tolower(b);
  if(a2 < b2)
    return true;
  else if(b2 < a2)
    return false;
  else return (a < b);
}

string mysort(string s, int len)
{
  char arr[len];
  for(int k=0; k<len; k++)
    arr[k] = s[k];
  for(int m=0; m<len-1; m++)
  {
    for(int n=m+1; n<len; n++)
    {
      if(lessthan(arr[n], arr[m]))
      {
        char tmp = arr[m];
        arr[m] = arr[n];
        arr[n] = tmp;
      }
    }
  }
  string result="";
  for(int z=0; z<len; z++)
    result+=arr[z];
  return result;
} 
